home *** CD-ROM | disk | FTP | other *** search
/ Aminet 40 / Aminet 40 (2000)(Schatztruhe)[!][Dec 2000].iso / Aminet / dev / lang / Python16_Src.lha / Python16_Source / Parser / pgen.c < prev    next >
Encoding:
C/C++ Source or Header  |  2000-08-03  |  14.6 KB  |  750 lines
  1. /* Parser generator */
  2. /* XXX This file is not yet fully PROTOized */
  3.  
  4. /* For a description, see the comments at end of this file */
  5.  
  6. #include "pgenheaders.h"
  7. #include "assert.h"
  8. #include "token.h"
  9. #include "node.h"
  10. #include "grammar.h"
  11. #include "metagrammar.h"
  12. #include "pgen.h"
  13.  
  14. extern int Py_DebugFlag;
  15.  
  16.  
  17. /* PART ONE -- CONSTRUCT NFA -- Cf. Algorithm 3.2 from [Aho&Ullman 77] */
  18.  
  19. typedef struct _nfaarc {
  20.     int    ar_label;
  21.     int    ar_arrow;
  22. } nfaarc;
  23.  
  24. typedef struct _nfastate {
  25.     int    st_narcs;
  26.     nfaarc    *st_arc;
  27. } nfastate;
  28.  
  29. typedef struct _nfa {
  30.     int        nf_type;
  31.     char        *nf_name;
  32.     int        nf_nstates;
  33.     nfastate    *nf_state;
  34.     int        nf_start, nf_finish;
  35. } nfa;
  36.  
  37. /* Forward */
  38. static void compile_rhs Py_PROTO((labellist *ll,
  39.                    nfa *nf, node *n, int *pa, int *pb));
  40. static void compile_alt Py_PROTO((labellist *ll,
  41.                    nfa *nf, node *n, int *pa, int *pb));
  42. static void compile_item Py_PROTO((labellist *ll,
  43.                 nfa *nf, node *n, int *pa, int *pb));
  44. static void compile_atom Py_PROTO((labellist *ll,
  45.                 nfa *nf, node *n, int *pa, int *pb));
  46.  
  47. static int
  48. addnfastate(nf)
  49.     nfa *nf;
  50. {
  51.     nfastate *st;
  52.     
  53.     PyMem_RESIZE(nf->nf_state, nfastate, nf->nf_nstates + 1);
  54.     if (nf->nf_state == NULL)
  55.         Py_FatalError("out of mem");
  56.     st = &nf->nf_state[nf->nf_nstates++];
  57.     st->st_narcs = 0;
  58.     st->st_arc = NULL;
  59.     return st - nf->nf_state;
  60. }
  61.  
  62. static void
  63. addnfaarc(nf, from, to, lbl)
  64.     nfa *nf;
  65.     int from, to, lbl;
  66. {
  67.     nfastate *st;
  68.     nfaarc *ar;
  69.     
  70.     st = &nf->nf_state[from];
  71.     PyMem_RESIZE(st->st_arc, nfaarc, st->st_narcs + 1);
  72.     if (st->st_arc == NULL)
  73.         Py_FatalError("out of mem");
  74.     ar = &st->st_arc[st->st_narcs++];
  75.     ar->ar_label = lbl;
  76.     ar->ar_arrow = to;
  77. }
  78.  
  79. static nfa *
  80. newnfa(name)
  81.     char *name;
  82. {
  83.     nfa *nf;
  84.     static int type = NT_OFFSET; /* All types will be disjunct */
  85.     
  86.     nf = PyMem_NEW(nfa, 1);
  87.     if (nf == NULL)
  88.         Py_FatalError("no mem for new nfa");
  89.     nf->nf_type = type++;
  90.     nf->nf_name = name; /* XXX strdup(name) ??? */
  91.     nf->nf_nstates = 0;
  92.     nf->nf_state = NULL;
  93.     nf->nf_start = nf->nf_finish = -1;
  94.     return nf;
  95. }
  96.  
  97. typedef struct _nfagrammar {
  98.     int        gr_nnfas;
  99.     nfa        **gr_nfa;
  100.     labellist    gr_ll;
  101. } nfagrammar;
  102.  
  103. /* Forward */
  104. static void compile_rule Py_PROTO((nfagrammar *gr, node *n));
  105.  
  106. static nfagrammar *
  107. newnfagrammar()
  108. {
  109.     nfagrammar *gr;
  110.     
  111.     gr = PyMem_NEW(nfagrammar, 1);
  112.     if (gr == NULL)
  113.         Py_FatalError("no mem for new nfa grammar");
  114.     gr->gr_nnfas = 0;
  115.     gr->gr_nfa = NULL;
  116.     gr->gr_ll.ll_nlabels = 0;
  117.     gr->gr_ll.ll_label = NULL;
  118.     addlabel(&gr->gr_ll, ENDMARKER, "EMPTY");
  119.     return gr;
  120. }
  121.  
  122. static nfa *
  123. addnfa(gr, name)
  124.     nfagrammar *gr;
  125.     char *name;
  126. {
  127.     nfa *nf;
  128.     
  129.     nf = newnfa(name);
  130.     PyMem_RESIZE(gr->gr_nfa, nfa *, gr->gr_nnfas + 1);
  131.     if (gr->gr_nfa == NULL)
  132.         Py_FatalError("out of mem");
  133.     gr->gr_nfa[gr->gr_nnfas++] = nf;
  134.     addlabel(&gr->gr_ll, NAME, nf->nf_name);
  135.     return nf;
  136. }
  137.  
  138. #ifdef Py_DEBUG
  139.  
  140. static char REQNFMT[] = "metacompile: less than %d children\n";
  141.  
  142. #define REQN(i, count) \
  143.      if (i < count) { \
  144.         fprintf(stderr, REQNFMT, count); \
  145.         Py_FatalError("REQN"); \
  146.     } else
  147.  
  148. #else
  149. #define REQN(i, count)    /* empty */
  150. #endif
  151.  
  152. static nfagrammar *
  153. metacompile(n)
  154.     node *n;
  155. {
  156.     nfagrammar *gr;
  157.     int i;
  158.     
  159.     printf("Compiling (meta-) parse tree into NFA grammar\n");
  160.     gr = newnfagrammar();
  161.     REQ(n, MSTART);
  162.     i = n->n_nchildren - 1; /* Last child is ENDMARKER */
  163.     n = n->n_child;
  164.     for (; --i >= 0; n++) {
  165.         if (n->n_type != NEWLINE)
  166.             compile_rule(gr, n);
  167.     }
  168.     return gr;
  169. }
  170.  
  171. static void
  172. compile_rule(gr, n)
  173.     nfagrammar *gr;
  174.     node *n;
  175. {
  176.     nfa *nf;
  177.     
  178.     REQ(n, RULE);
  179.     REQN(n->n_nchildren, 4);
  180.     n = n->n_child;
  181.     REQ(n, NAME);
  182.     nf = addnfa(gr, n->n_str);
  183.     n++;
  184.     REQ(n, COLON);
  185.     n++;
  186.     REQ(n, RHS);
  187.     compile_rhs(&gr->gr_ll, nf, n, &nf->nf_start, &nf->nf_finish);
  188.     n++;
  189.     REQ(n, NEWLINE);
  190. }
  191.  
  192. static void
  193. compile_rhs(ll, nf, n, pa, pb)
  194.     labellist *ll;
  195.     nfa *nf;
  196.     node *n;
  197.     int *pa, *pb;
  198. {
  199.     int i;
  200.     int a, b;
  201.     
  202.     REQ(n, RHS);
  203.     i = n->n_nchildren;
  204.     REQN(i, 1);
  205.     n = n->n_child;
  206.     REQ(n, ALT);
  207.     compile_alt(ll, nf, n, pa, pb);
  208.     if (--i <= 0)
  209.         return;
  210.     n++;
  211.     a = *pa;
  212.     b = *pb;
  213.     *pa = addnfastate(nf);
  214.     *pb = addnfastate(nf);
  215.     addnfaarc(nf, *pa, a, EMPTY);
  216.     addnfaarc(nf, b, *pb, EMPTY);
  217.     for (; --i >= 0; n++) {
  218.         REQ(n, VBAR);
  219.         REQN(i, 1);
  220.         --i;
  221.         n++;
  222.         REQ(n, ALT);
  223.         compile_alt(ll, nf, n, &a, &b);
  224.         addnfaarc(nf, *pa, a, EMPTY);
  225.         addnfaarc(nf, b, *pb, EMPTY);
  226.     }
  227. }
  228.  
  229. static void
  230. compile_alt(ll, nf, n, pa, pb)
  231.     labellist *ll;
  232.     nfa *nf;
  233.     node *n;
  234.     int *pa, *pb;
  235. {
  236.     int i;
  237.     int a, b;
  238.     
  239.     REQ(n, ALT);
  240.     i = n->n_nchildren;
  241.     REQN(i, 1);
  242.     n = n->n_child;
  243.     REQ(n, ITEM);
  244.     compile_item(ll, nf, n, pa, pb);
  245.     --i;
  246.     n++;
  247.     for (; --i >= 0; n++) {
  248.         if (n->n_type == COMMA) { /* XXX Temporary */
  249.             REQN(i, 1);
  250.             --i;
  251.             n++;
  252.         }
  253.         REQ(n, ITEM);
  254.         compile_item(ll, nf, n, &a, &b);
  255.         addnfaarc(nf, *pb, a, EMPTY);
  256.         *pb = b;
  257.     }
  258. }
  259.  
  260. static void
  261. compile_item(ll, nf, n, pa, pb)
  262.     labellist *ll;
  263.     nfa *nf;
  264.     node *n;
  265.     int *pa, *pb;
  266. {
  267.     int i;
  268.     int a, b;
  269.     
  270.     REQ(n, ITEM);
  271.     i = n->n_nchildren;
  272.     REQN(i, 1);
  273.     n = n->n_child;
  274.     if (n->n_type == LSQB) {
  275.         REQN(i, 3);
  276.         n++;
  277.         REQ(n, RHS);
  278.         *pa = addnfastate(nf);
  279.         *pb = addnfastate(nf);
  280.         addnfaarc(nf, *pa, *pb, EMPTY);
  281.         compile_rhs(ll, nf, n, &a, &b);
  282.         addnfaarc(nf, *pa, a, EMPTY);
  283.         addnfaarc(nf, b, *pb, EMPTY);
  284.         REQN(i, 1);
  285.         n++;
  286.         REQ(n, RSQB);
  287.     }
  288.     else {
  289.         compile_atom(ll, nf, n, pa, pb);
  290.         if (--i <= 0)
  291.             return;
  292.         n++;
  293.         addnfaarc(nf, *pb, *pa, EMPTY);
  294.         if (n->n_type == STAR)
  295.             *pb = *pa;
  296.         else
  297.             REQ(n, PLUS);
  298.     }
  299. }
  300.  
  301. static void
  302. compile_atom(ll, nf, n, pa, pb)
  303.     labellist *ll;
  304.     nfa *nf;
  305.     node *n;
  306.     int *pa, *pb;
  307. {
  308.     int i;
  309.     
  310.     REQ(n, ATOM);
  311.     i = n->n_nchildren;
  312.     REQN(i, 1);
  313.     n = n->n_child;
  314.     if (n->n_type == LPAR) {
  315.         REQN(i, 3);
  316.         n++;
  317.         REQ(n, RHS);
  318.         compile_rhs(ll, nf, n, pa, pb);
  319.         n++;
  320.         REQ(n, RPAR);
  321.     }
  322.     else if (n->n_type == NAME || n->n_type == STRING) {
  323.         *pa = addnfastate(nf);
  324.         *pb = addnfastate(nf);
  325.         addnfaarc(nf, *pa, *pb, addlabel(ll, n->n_type, n->n_str));
  326.     }
  327.     else
  328.         REQ(n, NAME);
  329. }
  330.  
  331. static void
  332. dumpstate(ll, nf, istate)
  333.     labellist *ll;
  334.     nfa *nf;
  335.     int istate;
  336. {
  337.     nfastate *st;
  338.     int i;
  339.     nfaarc *ar;
  340.     
  341.     printf("%c%2d%c",
  342.         istate == nf->nf_start ? '*' : ' ',
  343.         istate,
  344.         istate == nf->nf_finish ? '.' : ' ');
  345.     st = &nf->nf_state[istate];
  346.     ar = st->st_arc;
  347.     for (i = 0; i < st->st_narcs; i++) {
  348.         if (i > 0)
  349.             printf("\n    ");
  350.         printf("-> %2d  %s", ar->ar_arrow,
  351.             PyGrammar_LabelRepr(&ll->ll_label[ar->ar_label]));
  352.         ar++;
  353.     }
  354.     printf("\n");
  355. }
  356.  
  357. static void
  358. dumpnfa(ll, nf)
  359.     labellist *ll;
  360.     nfa *nf;
  361. {
  362.     int i;
  363.     
  364.     printf("NFA '%s' has %d states; start %d, finish %d\n",
  365.         nf->nf_name, nf->nf_nstates, nf->nf_start, nf->nf_finish);
  366.     for (i = 0; i < nf->nf_nstates; i++)
  367.         dumpstate(ll, nf, i);
  368. }
  369.  
  370.  
  371. /* PART TWO -- CONSTRUCT DFA -- Algorithm 3.1 from [Aho&Ullman 77] */
  372.  
  373. static void
  374. addclosure(ss, nf, istate)
  375.     bitset ss;
  376.     nfa *nf;
  377.     int istate;
  378. {
  379.     if (addbit(ss, istate)) {
  380.         nfastate *st = &nf->nf_state[istate];
  381.         nfaarc *ar = st->st_arc;
  382.         int i;
  383.         
  384.         for (i = st->st_narcs; --i >= 0; ) {
  385.             if (ar->ar_label == EMPTY)
  386.                 addclosure(ss, nf, ar->ar_arrow);
  387.             ar++;
  388.         }
  389.     }
  390. }
  391.  
  392. typedef struct _ss_arc {
  393.     bitset    sa_bitset;
  394.     int    sa_arrow;
  395.     int    sa_label;
  396. } ss_arc;
  397.  
  398. typedef struct _ss_state {
  399.     bitset    ss_ss;
  400.     int    ss_narcs;
  401.     ss_arc    *ss_arc;
  402.     int    ss_deleted;
  403.     int    ss_finish;
  404.     int    ss_rename;
  405. } ss_state;
  406.  
  407. typedef struct _ss_dfa {
  408.     int    sd_nstates;
  409.     ss_state *sd_state;
  410. } ss_dfa;
  411.  
  412. /* Forward */
  413. static void printssdfa Py_PROTO((int xx_nstates, ss_state *xx_state, int nbits,
  414.                   labellist *ll, char *msg));
  415. static void simplify Py_PROTO((int xx_nstates, ss_state *xx_state));
  416. static void convert Py_PROTO((dfa *d, int xx_nstates, ss_state *xx_state));
  417.  
  418. static void
  419. makedfa(gr, nf, d)
  420.     nfagrammar *gr;
  421.     nfa *nf;
  422.     dfa *d;
  423. {
  424.     int nbits = nf->nf_nstates;
  425.     bitset ss;
  426.     int xx_nstates;
  427.     ss_state *xx_state, *yy;
  428.     ss_arc *zz;
  429.     int istate, jstate, iarc, jarc, ibit;
  430.     nfastate *st;
  431.     nfaarc *ar;
  432.     
  433.     ss = newbitset(nbits);
  434.     addclosure(ss, nf, nf->nf_start);
  435.     xx_state = PyMem_NEW(ss_state, 1);
  436.     if (xx_state == NULL)
  437.         Py_FatalError("no mem for xx_state in makedfa");
  438.     xx_nstates = 1;
  439.     yy = &xx_state[0];
  440.     yy->ss_ss = ss;
  441.     yy->ss_narcs = 0;
  442.     yy->ss_arc = NULL;
  443.     yy->ss_deleted = 0;
  444.     yy->ss_finish = testbit(ss, nf->nf_finish);
  445.     if (yy->ss_finish)
  446.         printf("Error: nonterminal '%s' may produce empty.\n",
  447.             nf->nf_name);
  448.     
  449.     /* This algorithm is from a book written before
  450.        the invention of structured programming... */
  451.  
  452.     /* For each unmarked state... */
  453.     for (istate = 0; istate < xx_nstates; ++istate) {
  454.         yy = &xx_state[istate];
  455.         ss = yy->ss_ss;
  456.         /* For all its states... */
  457.         for (ibit = 0; ibit < nf->nf_nstates; ++ibit) {
  458.             if (!testbit(ss, ibit))
  459.                 continue;
  460.             st = &nf->nf_state[ibit];
  461.             /* For all non-empty arcs from this state... */
  462.             for (iarc = 0; iarc < st->st_narcs; iarc++) {
  463.                 ar = &st->st_arc[iarc];
  464.                 if (ar->ar_label == EMPTY)
  465.                     continue;
  466.                 /* Look up in list of arcs from this state */
  467.                 for (jarc = 0; jarc < yy->ss_narcs; ++jarc) {
  468.                     zz = &yy->ss_arc[jarc];
  469.                     if (ar->ar_label == zz->sa_label)
  470.                         goto found;
  471.                 }
  472.                 /* Add new arc for this state */
  473.                 PyMem_RESIZE(yy->ss_arc, ss_arc,
  474.                          yy->ss_narcs + 1);
  475.                 if (yy->ss_arc == NULL)
  476.                     Py_FatalError("out of mem");
  477.                 zz = &yy->ss_arc[yy->ss_narcs++];
  478.                 zz->sa_label = ar->ar_label;
  479.                 zz->sa_bitset = newbitset(nbits);
  480.                 zz->sa_arrow = -1;
  481.              found:    ;
  482.                 /* Add destination */
  483.                 addclosure(zz->sa_bitset, nf, ar->ar_arrow);
  484.             }
  485.         }
  486.         /* Now look up all the arrow states */
  487.         for (jarc = 0; jarc < xx_state[istate].ss_narcs; jarc++) {
  488.             zz = &xx_state[istate].ss_arc[jarc];
  489.             for (jstate = 0; jstate < xx_nstates; jstate++) {
  490.                 if (samebitset(zz->sa_bitset,
  491.                     xx_state[jstate].ss_ss, nbits)) {
  492.                     zz->sa_arrow = jstate;
  493.                     goto done;
  494.                 }
  495.             }
  496.             PyMem_RESIZE(xx_state, ss_state, xx_nstates + 1);
  497.             if (xx_state == NULL)
  498.                 Py_FatalError("out of mem");
  499.             zz->sa_arrow = xx_nstates;
  500.             yy = &xx_state[xx_nstates++];
  501.             yy->ss_ss = zz->sa_bitset;
  502.             yy->ss_narcs = 0;
  503.             yy->ss_arc = NULL;
  504.             yy->ss_deleted = 0;
  505.             yy->ss_finish = testbit(yy->ss_ss, nf->nf_finish);
  506.          done:    ;
  507.         }
  508.     }
  509.     
  510.     if (Py_DebugFlag)
  511.         printssdfa(xx_nstates, xx_state, nbits, &gr->gr_ll,
  512.                         "before minimizing");
  513.     
  514.     simplify(xx_nstates, xx_state);
  515.     
  516.     if (Py_DebugFlag)
  517.         printssdfa(xx_nstates, xx_state, nbits, &gr->gr_ll,
  518.                         "after minimizing");
  519.     
  520.     convert(d, xx_nstates, xx_state);
  521.     
  522.     /* XXX cleanup */
  523. }
  524.  
  525. static void
  526. printssdfa(xx_nstates, xx_state, nbits, ll, msg)
  527.     int xx_nstates;
  528.     ss_state *xx_state;
  529.     int nbits;
  530.     labellist *ll;
  531.     char *msg;
  532. {
  533.     int i, ibit, iarc;
  534.     ss_state *yy;
  535.     ss_arc *zz;
  536.     
  537.     printf("Subset DFA %s\n", msg);
  538.     for (i = 0; i < xx_nstates; i++) {
  539.         yy = &xx_state[i];
  540.         if (yy->ss_deleted)
  541.             continue;
  542.         printf(" Subset %d", i);
  543.         if (yy->ss_finish)
  544.             printf(" (finish)");
  545.         printf(" { ");
  546.         for (ibit = 0; ibit < nbits; ibit++) {
  547.             if (testbit(yy->ss_ss, ibit))
  548.                 printf("%d ", ibit);
  549.         }
  550.         printf("}\n");
  551.         for (iarc = 0; iarc < yy->ss_narcs; iarc++) {
  552.             zz = &yy->ss_arc[iarc];
  553.             printf("  Arc to state %d, label %s\n",
  554.                 zz->sa_arrow,
  555.                 PyGrammar_LabelRepr(
  556.                     &ll->ll_label[zz->sa_label]));
  557.         }
  558.     }
  559. }
  560.  
  561.  
  562. /* PART THREE -- SIMPLIFY DFA */
  563.  
  564. /* Simplify the DFA by repeatedly eliminating states that are
  565.    equivalent to another oner.  This is NOT Algorithm 3.3 from
  566.    [Aho&Ullman 77].  It does not always finds the minimal DFA,
  567.    but it does usually make a much smaller one...  (For an example
  568.    of sub-optimal behaviour, try S: x a b+ | y a b+.)
  569. */
  570.  
  571. static int
  572. samestate(s1, s2)
  573.     ss_state *s1, *s2;
  574. {
  575.     int i;
  576.     
  577.     if (s1->ss_narcs != s2->ss_narcs || s1->ss_finish != s2->ss_finish)
  578.         return 0;
  579.     for (i = 0; i < s1->ss_narcs; i++) {
  580.         if (s1->ss_arc[i].sa_arrow != s2->ss_arc[i].sa_arrow ||
  581.             s1->ss_arc[i].sa_label != s2->ss_arc[i].sa_label)
  582.             return 0;
  583.     }
  584.     return 1;
  585. }
  586.  
  587. static void
  588. renamestates(xx_nstates, xx_state, from, to)
  589.     int xx_nstates;
  590.     ss_state *xx_state;
  591.     int from, to;
  592. {
  593.     int i, j;
  594.     
  595.     if (Py_DebugFlag)
  596.         printf("Rename state %d to %d.\n", from, to);
  597.     for (i = 0; i < xx_nstates; i++) {
  598.         if (xx_state[i].ss_deleted)
  599.             continue;
  600.         for (j = 0; j < xx_state[i].ss_narcs; j++) {
  601.             if (xx_state[i].ss_arc[j].sa_arrow == from)
  602.                 xx_state[i].ss_arc[j].sa_arrow = to;
  603.         }
  604.     }
  605. }
  606.  
  607. static void
  608. simplify(xx_nstates, xx_state)
  609.     int xx_nstates;
  610.     ss_state *xx_state;
  611. {
  612.     int changes;
  613.     int i, j;
  614.     
  615.     do {
  616.         changes = 0;
  617.         for (i = 1; i < xx_nstates; i++) {
  618.             if (xx_state[i].ss_deleted)
  619.                 continue;
  620.             for (j = 0; j < i; j++) {
  621.                 if (xx_state[j].ss_deleted)
  622.                     continue;
  623.                 if (samestate(&xx_state[i], &xx_state[j])) {
  624.                     xx_state[i].ss_deleted++;
  625.                     renamestates(xx_nstates, xx_state,
  626.                              i, j);
  627.                     changes++;
  628.                     break;
  629.                 }
  630.             }
  631.         }
  632.     } while (changes);
  633. }
  634.  
  635.  
  636. /* PART FOUR -- GENERATE PARSING TABLES */
  637.  
  638. /* Convert the DFA into a grammar that can be used by our parser */
  639.  
  640. static void
  641. convert(d, xx_nstates, xx_state)
  642.     dfa *d;
  643.     int xx_nstates;
  644.     ss_state *xx_state;
  645. {
  646.     int i, j;
  647.     ss_state *yy;
  648.     ss_arc *zz;
  649.     
  650.     for (i = 0; i < xx_nstates; i++) {
  651.         yy = &xx_state[i];
  652.         if (yy->ss_deleted)
  653.             continue;
  654.         yy->ss_rename = addstate(d);
  655.     }
  656.     
  657.     for (i = 0; i < xx_nstates; i++) {
  658.         yy = &xx_state[i];
  659.         if (yy->ss_deleted)
  660.             continue;
  661.         for (j = 0; j < yy->ss_narcs; j++) {
  662.             zz = &yy->ss_arc[j];
  663.             addarc(d, yy->ss_rename,
  664.                 xx_state[zz->sa_arrow].ss_rename,
  665.                 zz->sa_label);
  666.         }
  667.         if (yy->ss_finish)
  668.             addarc(d, yy->ss_rename, yy->ss_rename, 0);
  669.     }
  670.     
  671.     d->d_initial = 0;
  672. }
  673.  
  674.  
  675. /* PART FIVE -- GLUE IT ALL TOGETHER */
  676.  
  677. static grammar *
  678. maketables(gr)
  679.     nfagrammar *gr;
  680. {
  681.     int i;
  682.     nfa *nf;
  683.     dfa *d;
  684.     grammar *g;
  685.     
  686.     if (gr->gr_nnfas == 0)
  687.         return NULL;
  688.     g = newgrammar(gr->gr_nfa[0]->nf_type);
  689.             /* XXX first rule must be start rule */
  690.     g->g_ll = gr->gr_ll;
  691.     
  692.     for (i = 0; i < gr->gr_nnfas; i++) {
  693.         nf = gr->gr_nfa[i];
  694.         if (Py_DebugFlag) {
  695.             printf("Dump of NFA for '%s' ...\n", nf->nf_name);
  696.             dumpnfa(&gr->gr_ll, nf);
  697.         }
  698.         printf("Making DFA for '%s' ...\n", nf->nf_name);
  699.         d = adddfa(g, nf->nf_type, nf->nf_name);
  700.         makedfa(gr, gr->gr_nfa[i], d);
  701.     }
  702.     
  703.     return g;
  704. }
  705.  
  706. grammar *
  707. pgen(n)
  708.     node *n;
  709. {
  710.     nfagrammar *gr;
  711.     grammar *g;
  712.     
  713.     gr = metacompile(n);
  714.     g = maketables(gr);
  715.     translatelabels(g);
  716.     addfirstsets(g);
  717.     return g;
  718. }
  719.  
  720.  
  721. /*
  722.  
  723. Description
  724. -----------
  725.  
  726. Input is a grammar in extended BNF (using * for repetition, + for
  727. at-least-once repetition, [] for optional parts, | for alternatives and
  728. () for grouping).  This has already been parsed and turned into a parse
  729. tree.
  730.  
  731. Each rule is considered as a regular expression in its own right.
  732. It is turned into a Non-deterministic Finite Automaton (NFA), which
  733. is then turned into a Deterministic Finite Automaton (DFA), which is then
  734. optimized to reduce the number of states.  See [Aho&Ullman 77] chapter 3,
  735. or similar compiler books (this technique is more often used for lexical
  736. analyzers).
  737.  
  738. The DFA's are used by the parser as parsing tables in a special way
  739. that's probably unique.  Before they are usable, the FIRST sets of all
  740. non-terminals are computed.
  741.  
  742. Reference
  743. ---------
  744.  
  745. [Aho&Ullman 77]
  746.     Aho&Ullman, Principles of Compiler Design, Addison-Wesley 1977
  747.     (first edition)
  748.  
  749. */
  750.